//Given an array nums of n integers where nums[i] is in the range [1, n], 
//return an array of all the integers in the range [1, n] that do not appear in nums. 
//
// 
// Example 1: 
// Input: nums = [4,3,2,7,8,2,3,1]
//Output: [5,6]
// Example 2: 
// Input: nums = [1,1]
//Output: [2]
// 
// 
// Constraints: 
//
// 
// n == nums.length 
// 1 <= n <= 10⁵ 
// 1 <= nums[i] <= n 
// 
//
// 
// Follow up: Could you do it without extra space and in O(n) runtime? You may 
//assume the returned list does not count as extra space. 
// Related Topics Array Hash Table 👍 5062 👎 335


package leetcode.editor.en;

import java.util.ArrayList;
import java.util.List;

public class _448_FindAllNumbersDisappearedInAnArray {
    public static void main(String[] args) {
        Solution solution = new _448_FindAllNumbersDisappearedInAnArray().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> findDisappearedNumbers(int[] nums) {
            int l = nums.length;
            for (int i = 0; i < l; i++) {
                int x = (nums[i]-1) % l;
                nums[x]+=l;
            }
            List<Integer> r = new ArrayList<>();
            for (int i = 0; i < l; i++) {
                if (nums[i]<=l) {
                    r.add(i+1);
                }
            }
            return r;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}